Class HashedArrayList<T>

A list collection based on a plain dynamic array data structure. Expansion of the internal array is performed by doubling on demand. The internal array is only shrinked by the Clear method. When the FIFO property is set to false this class works fine as a stack of T. When the FIFO property is set to true the class will function as a (FIFO) queue but very inefficiently, use a LinkedList (LinkedList<T>) instead.

Implements

IEnumerable<T>, System.Collections.IEnumerable, System.IFormattable, System.ICloneable, System.IDisposable, System.Collections.Generic.IList<T>, System.Collections.Generic.ICollection<T>, ICollection<T>, ICollectionValue<T>, IDirectedCollectionValue<T>, IDirectedEnumerable<T>, IExtensible<T>, IIndexed<T>, IList<T>, ISequenced<T>, IShowable

Bases

object, EnumerableBase<T>, CollectionValueBase<T>, CollectionBase<T>, DirectedCollectionBase<T>, SequencedBase<T>, ArrayBase<T>

Field overview

array, Inherited from ArrayBase<T> ,
isReadOnlyBase, Inherited from CollectionBase<T> ,
itemequalityComparer, Inherited from CollectionBase<T> ,
offset, Inherited from ArrayBase<T> ,
size, Inherited from CollectionBase<T> ,
stamp, Inherited from CollectionBase<T>

Event overview

CollectionChanged, Inherited from CollectionValueBase<T> ,
CollectionCleared, Inherited from CollectionValueBase<T> ,
ItemInserted, Inherited from CollectionValueBase<T> ,
ItemRemovedAt, Inherited from CollectionValueBase<T> ,
ItemsAdded, Inherited from CollectionValueBase<T> ,
ItemsRemoved, Inherited from CollectionValueBase<T>

Property overview

ActiveEvents, Inherited from CollectionValueBase<T> ,
AllowsDuplicates ,
ContainsSpeed ,
Count ,
CountSpeed, Inherited from CollectionBase<T> ,
Direction, Inherited from SequencedBase<T> ,
DuplicatesByCounting ,
EqualityComparer, Inherited from CollectionBase<T> ,
FIFO ,
First ,
IndexingSpeed ,
IsEmpty, Inherited from CollectionBase<T> ,
IsFixedSize ,
IsReadOnly, Inherited from CollectionBase<T> ,
IsValid ,
this[int index] ,
this[int start, int count], Inherited from ArrayBase<T> ,
Last ,
ListenableEvents ,
Offset ,
SyncRoot, Inherited from CollectionBase<T> ,
Underlying ,
underlyingsize

Constructor overview

HashedArrayList<T>() ,
HashedArrayList<T>(System.Collections.Generic.IEqualityComparer<T> itemequalityComparer) ,
HashedArrayList<T>(int capacity) ,
HashedArrayList<T>(int capacity, System.Collections.Generic.IEqualityComparer<T> itemequalityComparer)

Method overview

Add(T item) ,
AddAll<U>(IEnumerable<U> items) ,
All(Fun<T,bool> predicate), Inherited from CollectionValueBase<T> ,
Apply(Act<T> action), Inherited from CollectionValueBase<T> ,
Backwards(), Inherited from ArrayBase<T> ,
Check() ,
checkRange(int start, int count), Inherited from CollectionBase<T> ,
Choose(), Inherited from ArrayBase<T> ,
Clear() ,
Clone() ,
Contains(T item) ,
ContainsAll<U>(IEnumerable<U> items) ,
ContainsCount(T item) ,
CopyTo(T[] array, int index), Inherited from CollectionValueBase<T> ,
Dispose() ,
Equals(object obj), Inherited from object ,
Exists(Fun<T,bool> predicate), Inherited from CollectionValueBase<T> ,
expand() ,
expand(int newcapacity, int newsize) ,
Filter(Fun<T,bool> predicate), Inherited from CollectionValueBase<T> ,
Finalize(), Inherited from object ,
Find(ref T item) ,
Find(Fun<T,bool> predicate, out T item), Inherited from CollectionValueBase<T> ,
FindAll(Fun<T,bool> filter) ,
FindIndex(Fun<T,bool> predicate), Inherited from SequencedBase<T> ,
FindLast(Fun<T,bool> predicate, out T item), Inherited from DirectedCollectionBase<T> ,
FindLastIndex(Fun<T,bool> predicate), Inherited from SequencedBase<T> ,
FindOrAdd(ref T item) ,
GetEnumerator() ,
GetHashCode(), Inherited from object ,
GetSequencedHashCode(), Inherited from SequencedBase<T> ,
GetType(), Inherited from object ,
GetUnsequencedHashCode() ,
IndexOf(T item) ,
insert(int i, T item) ,
Insert(int index, T item) ,
Insert(IList<T> pointer, T item) ,
InsertAll<U>(int index, IEnumerable<U> items) ,
InsertFirst(T item) ,
InsertLast(T item) ,
IsSorted() ,
IsSorted(System.Collections.Generic.IComparer<T> c) ,
ItemMultiplicities() ,
LastIndexOf(T item) ,
LastViewOf(T item) ,
Map<V>(Fun<T,V> mapper) ,
Map<V>(Fun<T,V> mapper, System.Collections.Generic.IEqualityComparer<V> itemequalityComparer) ,
MemberwiseClone(), Inherited from object ,
modifycheck(int stamp) ,
raiseCollectionChanged(), Inherited from CollectionValueBase<T> ,
raiseCollectionCleared(bool full, int count), Inherited from CollectionValueBase<T> ,
raiseCollectionCleared(bool full, int count, System.Nullable<int> offset), Inherited from CollectionValueBase<T> ,
raiseForAdd(T item), Inherited from CollectionValueBase<T> ,
raiseForInsert(int i, T item), Inherited from CollectionValueBase<T> ,
raiseForRemove(T item), Inherited from CollectionValueBase<T> ,
raiseForRemove(T item, int count), Inherited from CollectionValueBase<T> ,
raiseForRemoveAll(ICollectionValue<T> wasRemoved), Inherited from CollectionValueBase<T> ,
raiseForRemoveAt(int index, T item), Inherited from CollectionValueBase<T> ,
raiseForSetThis(int index, T value, T item), Inherited from CollectionValueBase<T> ,
raiseForUpdate(T newitem, T olditem), Inherited from CollectionValueBase<T> ,
raiseForUpdate(T newitem, T olditem, int count), Inherited from CollectionValueBase<T> ,
raiseItemInserted(T item, int index), Inherited from CollectionValueBase<T> ,
raiseItemRemovedAt(T item, int index), Inherited from CollectionValueBase<T> ,
raiseItemsAdded(T item, int count), Inherited from CollectionValueBase<T> ,
raiseItemsRemoved(T item, int count), Inherited from CollectionValueBase<T> ,
Remove() ,
Remove(T item) ,
Remove(T item, out T removeditem) ,
RemoveAll<U>(IEnumerable<U> items) ,
RemoveAllCopies(T item) ,
RemoveAt(int index) ,
RemoveFirst() ,
RemoveInterval(int start, int count) ,
RemoveLast() ,
RetainAll<U>(IEnumerable<U> items) ,
Reverse() ,
SequencedEquals(ISequenced<T> otherCollection), Inherited from SequencedBase<T> ,
Show(System.Text.StringBuilder stringbuilder, ref int rest, System.IFormatProvider formatProvider), Inherited from CollectionValueBase<T> ,
Shuffle() ,
Shuffle(System.Random rnd) ,
Slide(int offset) ,
Slide(int offset, int size) ,
Sort() ,
Sort(System.Collections.Generic.IComparer<T> comparer) ,
Span(IList<T> otherView) ,
ToArray(), Inherited from ArrayBase<T> ,
ToString(string format, System.IFormatProvider formatProvider), Inherited from CollectionValueBase<T> ,
ToString(), Inherited from CollectionValueBase<T> ,
TrySlide(int offset) ,
TrySlide(int offset, int size) ,
UniqueItems() ,
UnsequencedEquals(ICollection<T> that) ,
Update(T item) ,
Update(T item, out T olditem) ,
updatecheck() ,
UpdateOrAdd(T item) ,
UpdateOrAdd(T item, out T olditem) ,
View(int start, int count) ,
ViewOf(T item)

Property details

bool AllowsDuplicatesAccess: Read-Only

Value:True, indicating array list has bag semantics.

Speed ContainsSpeedAccess: Read-Only

Value:Speed.Linear

The value is symbolic indicating the type of asymptotic complexity in terms of the size of this collection (worst-case or amortized as relevant).
int CountAccess: Read-Only

Value:The number of items in this collection

bool DuplicatesByCountingAccess: Read-Only

Value:True if only one representative of a group of equal items is kept in the collection together with the total count.

By convention this is true for any collection with set semantics.
bool FIFOAccess: Read-Write

Value:True if the Remove() operation removes from the start of the list, false if it removes from the end. The default for a new array list is false.

Since Add(T item) always add at the end of the list, this describes if list has FIFO or LIFO semantics.
T FirstAccess: Read-Only

Value:The first item in this list.

Throws
NoSuchItemException if this list is empty.
Speed IndexingSpeedAccess: Read-Only

Value:

bool IsFixedSizeAccess: Read-Only
bool IsValidAccess: Read-Only

Value:

T this[int index]Access: Read-Write

Value:The index'th item of this list.

On this list, this indexer is read/write.
Throws
System.IndexOutOfRangeException if index is negative or >= the size of the collection.
DuplicateNotAllowedException By the get operation if the item already is present somewhere else in the list.
Parameters:
index:The index of the item to fetch or store.
T LastAccess: Read-Only

Value:The last item in this list.

Throws
NoSuchItemException if this list is empty.
EventTypeEnum ListenableEventsAccess: Read-Only

Value:

int OffsetAccess: Read-Only

Value:Offset for this list view or 0 for an underlying list.

IList<T> UnderlyingAccess: Read-Only

Value:Underlying list for view.

Null if this list is not a view.
int underlyingsizeAccess: Read-Only
The size of the underlying list.

Constructor details

HashedArrayList<T>() Create an array list with default item equalityComparer and initial capacity 8 items.
HashedArrayList<T>(System.Collections.Generic.IEqualityComparer<T> itemequalityComparer) Create an array list with external item equalityComparer and initial capacity 8 items.
Parameters:
itemequalityComparer:The external item equalityComparer
HashedArrayList<T>(int capacity) Create an array list with default item equalityComparer and prescribed initial capacity.
Parameters:
capacity:The prescribed capacity
HashedArrayList<T>(int capacity, System.Collections.Generic.IEqualityComparer<T> itemequalityComparer) Create an array list with external item equalityComparer and prescribed initial capacity.
Parameters:
capacity:The prescribed capacity
itemequalityComparer:The external item equalityComparer

Method details

bool Add(T item) Add an item to end of this list.
Returns:True
Parameters:
item:The item to add.
void AddAll<U>(IEnumerable<U> items) Add the elements from another collection to this collection.
Type parameters:
U
Constraints:
U : T
Parameters:
items:
bool Check() Check the integrity of the internal data structures of this array list.
Returns:True if check does not fail.
void Clear() Remove all items from this collection, resetting internal array size.
object Clone() Make a shallow copy of this HashedArrayList.
Returns:
bool Contains(T item) Check if this collection contains (an item equivalent to according to the itemequalityComparer) a particular value.
Returns:True if the items is in this collection.
Parameters:
item:The value to check for.
bool ContainsAll<U>(IEnumerable<U> items) Check if this collection contains all the values in another collection, taking multiplicities into account. Current implementation is not optimal.
Type parameters:
U
Constraints:
U : T
Returns:True if all values in itemsis in this collection.
Parameters:
items:The
int ContainsCount(T item) Count the number of items of the collection equal to a particular value. Returns 0 if and only if the value is not in the collection.
Returns:The number of copies found.
Parameters:
item:The value to count.
void Dispose() Invalidate this list. If a view, just invalidate the view. If not a view, invalidate the list and all views on it.
P void expand() Double the size of the internal array.
P void expand(int newcapacity, int newsize) Expand the internal array, resetting the index of the first unused element.
Parameters:
newcapacity:The new capacity (will be rouded upwards to a power of 2).
newsize:The new count of
bool Find(ref T item) Check if this collection contains an item equivalent according to the itemequalityComparer to a particular value. If so, return in the ref argument (a binary copy of) the actual value found.
Returns:True if the items is in this collection.
Parameters:
item:The value to look for.
IList<T> FindAll(Fun<T,bool> filter) Create a new list consisting of the items of this list satisfying a certain predicate.

The new list will be of type HashedArrayList

Returns:The new list.
Parameters:
filter:The filter delegate defining the predicate.
bool FindOrAdd(ref T item) Check if this collection contains an item equivalent according to the itemequalityComparer to a particular value. If so, return in the ref argument (a binary copy of) the actual value found. Else, add the item to the collection.
Returns:True if the item was found (hence not added).
Parameters:
item:The value to look for.
System.Collections.Generic.IEnumerator<T> GetEnumerator() Create an enumerator for the collection
Returns:The enumerator
int GetUnsequencedHashCode()
Returns:
int IndexOf(T item) Search for an item in the list going forwrds from the start.
Returns:Index of item from start.
Parameters:
item:Item to search for.
P void insert(int i, T item) Internal version of Insert with no modification checks.
Throws
DuplicateNotAllowedException if item already in list.
Parameters:
i:Index to insert at
item:Item to insert
void Insert(int index, T item) Insert an item at a specific index location in this list.
Throws
System.IndexOutOfRangeException if index is negative or > the size of the collection.
DuplicateNotAllowedException If the item is already present in the list.
Parameters:
index:The index at which to insert.
item:The item to insert.
F void Insert(IList<T> pointer, T item) Insert an item at the end of a compatible view, used as a pointer.

The pointer must be a view on the same list as this and the endpoitn of pointer must be a valid insertion point of this

Throws
IncompatibleViewExceptionIf pointer is not a view on or the same list as this
System.IndexOutOfRangeException?????? if the endpoint of pointer is not inside this
DuplicateNotAllowedException if the list has AllowsDuplicates==false and the item is already in the list.
Parameters:
pointer:
item:
void InsertAll<U>(int index, IEnumerable<U> items) Insert into this list all items from an enumerable collection starting at a particular index.
Throws
System.IndexOutOfRangeException if index is negative or > the size of the collection.
DuplicateNotAllowedException If items contains duplicates or some item already present in the list.
Parameters:
index:Index to start inserting at
items:Items to insert
void InsertFirst(T item) Insert an item at the front of this list;
Throws
DuplicateNotAllowedExceptionIf the item is already in the list
Parameters:
item:The item to insert.
void InsertLast(T item) Insert an item at the back of this list.
Throws
DuplicateNotAllowedExceptionIf the item is already in the list
Parameters:
item:The item to insert.
F bool IsSorted() Check if this list is sorted according to the default sorting order for the item type T, as defined by the Comparer<T> class
Throws
NotComparableExceptionif T is not comparable
Returns:True if the list is sorted, else false.
bool IsSorted(System.Collections.Generic.IComparer<T> c) Check if this list is sorted according to a specific sorting order.
Returns:True if the list is sorted, else false.
Parameters:
c:The comparer defining the sorting order.
ICollectionValue<KeyValuePair<T,int>> ItemMultiplicities()
Returns:
int LastIndexOf(T item) Search for an item in the list going backwords from the end.
Returns:Index of item from the end.
Parameters:
item:Item to search for.
IList<T> LastViewOf(T item) Create a list view on this list containing the last occurrence of a particular item.

Returns null if the item is not in this list.

Returns:The new list view.
Parameters:
item:The item to find.
IList<V> Map<V>(Fun<T,V> mapper) Create a new list consisting of the results of mapping all items of this list. The new list will use the default item equalityComparer for the item type V.

The new list will be of type HashedArrayList

Throws
DuplicateNotAllowedExceptionIf mapper creates duplicates
Type parameters:
VThe type of items of the new list
Returns:The new list.
Parameters:
mapper:The delegate defining the map.
IList<V> Map<V>(Fun<T,V> mapper, System.Collections.Generic.IEqualityComparer<V> itemequalityComparer) Create a new list consisting of the results of mapping all items of this list. The new list will use a specified item equalityComparer for the item type.

The new list will be of type HashedArrayList

Throws
DuplicateNotAllowedExceptionIf mapper creates duplicates
Type parameters:
VThe type of items of the new list
Returns:The new list.
Parameters:
mapper:The delegate defining the map.
itemequalityComparer:The item equalityComparer to use for the new list
P void modifycheck(int stamp) Check that the list has not been updated since a particular time.

To be used by enumerators and range

Throws
ViewDisposedException If check fails by this list being a disposed view.
CollectionModifiedExceptionIf the list *has* beeen updated since that time..
Parameters:
stamp:The stamp indicating the time.
T Remove() Remove one item from the list: from the front if FIFO is true, else from the back.
Throws
NoSuchItemException if this list is empty.
Returns:The removed item.
bool Remove(T item) Remove a particular item from this list. The item will be searched for from the end of the list if FIFO == false (the default), else from the start.
Returns:True if the item was found (and removed).
Parameters:
item:The value to remove.
bool Remove(T item, out T removeditem) Remove the first copy of a particular item from this collection if found. If an item was removed, report a binary copy of the actual item removed in the argument. The item will be searched for from the end of the list if FIFO == false (the default), else from the start.
Returns:True if the item was found (and removed).
Parameters:
item:The value to remove.
removeditem:The removed value.
void RemoveAll<U>(IEnumerable<U> items) Remove all items in another collection from this one, taking multiplicities into account. Matching items will be removed from the front. Current implementation is not optimal.
Type parameters:
U
Constraints:
U : T
Parameters:
items:The items to remove.
void RemoveAllCopies(T item) Remove all items equal to a given one.
Parameters:
item:The value to remove.
T RemoveAt(int index) Remove the item at a specific position of the list.
Throws
System.IndexOutOfRangeException if index is negative or >= the size of the collection.
Returns:The removed item.
Parameters:
index:The index of the item to remove.
T RemoveFirst() Remove one item from the fromnt of the list.
Throws
NoSuchItemException if this list is empty.
Returns:The removed item.
void RemoveInterval(int start, int count) Remove all items in an index interval.
Throws
System.ArgumentOutOfRangeExceptionIf start and count does not describe a valid interval in the list
Parameters:
start:The index of the first item to remove.
count:The number of items to remove.
T RemoveLast() Remove one item from the back of the list.
Throws
NoSuchItemException if this list is empty.
Returns:The removed item.
void RetainAll<U>(IEnumerable<U> items) Remove all items not in some other collection from this one, taking multiplicities into account. Items are retained front first.
Type parameters:
U
Constraints:
U : T
Parameters:
items:The items to retain.
void Reverse() Reverst the list so the items are in the opposite sequence order.
void Shuffle() Randomly shuffle the items of this list.
void Shuffle(System.Random rnd) Shuffle the items of this list according to a specific random source.
Parameters:
rnd:The random source.
IList<T> Slide(int offset) Slide this list view along the underlying list.
Throws
NotAViewException if this list is not a view.
System.ArgumentOutOfRangeException if the operation would bring either end of the view outside the underlying list.
Parameters:
offset:The signed amount to slide: positive to slide towards the end.
IList<T> Slide(int offset, int size) Slide this list view along the underlying list, changing its size.
Throws
NotAViewException if this list is not a view.
System.ArgumentOutOfRangeException if the operation would bring either end of the view outside the underlying list.
Parameters:
offset:The signed amount to slide: positive to slide towards the end.
size:The new size of the view.
void Sort() Sort the items of the list according to the default sorting order for the item type T, as defined by the Comparer[T] class (Comparer<T>).
Throws
System.InvalidOperationExceptionif T is not comparable
void Sort(System.Collections.Generic.IComparer<T> comparer) Sort the items of the list according to a specific sorting order.
Parameters:
comparer:The comparer defining the sorting order.
IList<T> Span(IList<T> otherView)

Returns null if otherView is strictly to the left of this view

Throws
IncompatibleViewExceptionIf otherView does not have the same underlying list as this
Returns:
Parameters:
otherView:
bool TrySlide(int offset)
Throws
NotAViewException if this list is not a view.
Returns:
Parameters:
offset:
bool TrySlide(int offset, int size)
Throws
NotAViewException if this list is not a view.
Returns:
Parameters:
offset:
size:
ICollectionValue<T> UniqueItems()
Returns:
bool UnsequencedEquals(ICollection<T> that)
Returns:
Parameters:
that:
bool Update(T item) Check if this collection contains an item equivalent according to the itemequalityComparer to a particular value. If so, update the item in the collection to with a binary copy of the supplied value. This will only update the first mathching item.
Returns:True if the item was found and hence updated.
Parameters:
item:Value to update.
bool Update(T item, out T olditem)
Returns:
Parameters:
item:
olditem:
P void updatecheck() Check if it is valid to perform updates and increment stamp if so.
Throws
ViewDisposedException If check fails by this list being a disposed view.
ReadOnlyCollectionException If check fails by this being a read only list.
bool UpdateOrAdd(T item) Check if this collection contains an item equivalent according to the itemequalityComparer to a particular value. If so, update the item in the collection to with a binary copy of the supplied value. This will only update the first mathching item.
Returns:True if the item was found and hence updated.
Parameters:
item:Value to update.
bool UpdateOrAdd(T item, out T olditem)
Returns:
Parameters:
item:
olditem:
IList<T> View(int start, int count) Create a list view on this list.
Throws
System.ArgumentOutOfRangeException if the start or count is negative or the range does not fit within list.
Returns:The new list view.
Parameters:
start:The index in this list of the start of the view.
count:The size of the view.
IList<T> ViewOf(T item) Create a list view on this list containing the (first) occurrence of a particular item.

Returns null if the item is not in this list.

Returns:The new list view.
Parameters:
item:The item to find.